#include "leecode.h"

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

template<typename T>
ostream& operator << (ostream& o, const vector<T>& vec) {
  for(auto v: vec)
    o << v << ",";        
  return o;
}


class MinCoins{

public:
  int coinChange(const vector<int>& coins, int account) {
    if(account == 0)
        return 0;
    for(int coin: coins)
      min_coins[coin] = 1;
    return getMinCoins(account, coins);
  }
  
  int getMinCoins(int account, const vector<int>& coins) {
    auto iter = min_coins.find(account);
    if(iter != min_coins.end())
      return iter->second;

    cout << "min coin account " << account << endl;

    int min_count = -1;
    for(int coin: coins) {
      if(coin < account) {
        cout << "getMinCoins " << account << endl;
        int temp = getMinCoins(account - coin, coins);
        if(temp == -1)
          continue;
        if(min_count != -1)
          min_count = min(min_count, 1 + temp);
        else {
          min_count = temp + 1;
        }
      }
    } 

    if(min_count != -1) {
      min_coins[account] = min_count;
      cout << "  count " << min_count << endl;
    }

    return min_count;
  }

  void expect(int account, const vector<int>& coins, int result) {
    int ret = coinChange(coins, account);
    if(ret == result)
      cout << "result correct for account  " << account
           << "  coins: " << coins
           << "  result: " << result << endl;
    else {
      cout << "result wrong for account  " << account
           << "  coins: " << coins 
           << "  expect:" << result
           <<  "  result: " << ret << endl;
    }
  }
private:
  unordered_map<int, int> min_coins;
};

// [186,419,83,408]
// 6249

void leecode() {
  MinCoins().expect(6249, {186,419,83,408}, 3);
}

